public class MySort {
    public static void mergeSort(int[] array){
          mergeSortFunc(array , 0 , array.length-1);
    }
    private static void mergeSortFunc(int[] array , int left , int right){
        if(left >= right) return  ;
        int mid = (left + right)/2 ;
        mergeSortFunc(array , left , mid);
        mergeSortFunc(array , mid+1 , right);
        merge(array , left , right , mid);
    }

    private static void merge(int[] array, int left, int right, int mid) {
          int s1 = left ;
          int s2 = mid + 1 ;
          //临时数组
          int[]  tmpArr = new int[right - left+1] ;
          int k = 0 ;

          //int e1 = mid ;    end1和end2都可以不定义，
          //int e2 = right ;
        //条件：两个子序都同时有数据
        while(s1 <= mid && s2 <= right){
          if(array[s2] <= array[s1]){
            tmpArr[k++] = array[s2++];
          }else{
              tmpArr[k++] = array[s1++];
          }
        }
        while(s1 <= mid){
            tmpArr[k++] = array[s1++];
        }
        while(s2 <= right){
            tmpArr[k++] = array[s2++];
        }
        //把临时数组放到序列中，用i+left解决范围问题
        for (int i = 0 ; i < tmpArr.length; i++) {
            array[i+left] = tmpArr[i];
        }
    }

    public static void mergeSortNor(int[] array){
        int gap = 1 ;
        while (gap < array.length){
            for (int i = 0; i < array.length; i+=2*gap) {
              int left = i ;
              int mid = left+gap-1 ;
              int right = mid+gap ;
              if(mid >= array.length){
                  mid = array.length-1 ;
              }
              if(right >= array.length){
                  right = array.length - 1;
              }
               merge(array ,left , right , mid);
            }
           gap *= 2 ;
        }
    }



}
